package org.basic.structure.arrays;

/**
 * 排序算法
 *
 * @author LiKun
 * @date 2021/10/4 16:31
 */
public final class SortAlgorithm {
    /**
     * 冒泡排序算法
     * 原理：每次将剩余未排序的最大值移动到该段数组(未排序数组)的最后
     *
     * @param target 待排序数据
     */
    public void bubbleSort(int[] target) {
        // i：已排序/正在排序数据的个数
        for (int i = 1; i < target.length; i++) {
            // 游标位置索引
            for (int j = 0; j < target.length - i; j++) {
                // 如果后面的数据大于前面的数据，则将其互换位置
                if (target[j] > target[j + 1]) {
                    // 交换 target[j] 和 target[j + 1] 的数据
                    this.swap(target, j, j + 1);
                }
            }
        }
    }

    /*----------------------------------------------------------------------------------------------------------------*/

    /**
     * 快速排序算法
     * 原理：随机选取一个基数，之后将小于该基数的数据移动到其左面，将大于该基数的数据移动到其右面；之后递归处理左面的数组和右面的数组
     *
     * @param target 待排序数组
     */
    public void quickSort(int[] target) {
        if (target.length > 1) {
            // 处理排序逻辑
            quickSortRecursive(target, 0, target.length - 1);
        }
    }

    /*------------------------------------------------private methods-------------------------------------------------*/

    /**
     * 交换给定数组(target)中索引为left和right的数据值
     *
     * @param target 待交换数组
     * @param left   数组索引
     * @param right  数组索引
     */
    private void swap(int[] target, int left, int right) {
        int virtual = target[left];
        target[left] = target[right];
        target[right] = virtual;
    }

    /**
     * 递归处理快速排序
     *
     * @param values     待排序数据
     * @param leftIndex  本轮排序左边界
     * @param rightIndex 本轮排序右边界
     */
    private void quickSortRecursive(int[] values, int leftIndex, int rightIndex) {
        if (leftIndex < rightIndex) {
            int left = leftIndex;
            int right = rightIndex;
            int index = values[leftIndex];

            do {
                while (right > left && values[right] >= index) {
                    right--;
                }

                if (right > left) {
                    this.swap(values, left++, right);
                }

                while (right > left && values[left] <= index) {
                    left++;
                }

                if (right > left) {
                    this.swap(values, left, right--);
                }
            } while (right > left);

            this.quickSortRecursive(values, leftIndex, left - 1);
            this.quickSortRecursive(values, right + 1, rightIndex);
        }
    }
}
